using dtPolyRef = System.UInt32;
using dtTileRef = System.UInt32;
using dtStatus = System.UInt32;

namespace Recast
{
	public unsafe partial class RecastGlobal
	{
		public unsafe partial class dtNavMesh
		{
			public dtNavMeshParams* m_Params;
			public float* m_orig;// [3];
			public float m_tileWidth;
			public float m_tileHeight;
			public int m_maxTiles;
			public int m_tileLutSize;
			public int m_tileLutMask;
			public dtMeshTile** m_posLookup;
			public dtMeshTile* m_nextFree;
			public dtMeshTile* m_tiles;
			public uint m_saltBits;
			public uint m_tileBits;
			public uint m_polyBits;
			//ublic friend class dtNavMeshQuery;
			public dtNavMesh()
			{
				m_saltBits = 0;
				m_tileBits = 0;
				m_polyBits = 0;
				m_Params = rcNew<dtNavMeshParams>(rcAllocHint.RC_ALLOC_PERM);
				memset(m_Params, 0, sizeof(dtNavMeshParams));
				m_orig = rcNewArray<float>(3, rcAllocHint.RC_ALLOC_PERM);
				m_orig[0] = 0;
				m_orig[1] = 0;
				m_orig[2] = 0;
			}
			~dtNavMesh()
			{
				for (int i = 0; i < m_maxTiles; ++i)
				{
					if (0 != (m_tiles[i].flags & (int)dtTileFlags.DT_TILE_FREE_DATA))
					{
						dtFree(m_tiles[i].data);
						m_tiles[i].data = (byte*)0;
						m_tiles[i].dataSize = 0;
					}
				}
				dtFree(m_posLookup);
				dtFree(m_tiles);
				dtFree(m_orig);
				dtFree(m_Params);
			}
			public dtStatus init(dtNavMeshParams* Params)
			{
				memcpy(m_Params, Params, sizeof(dtNavMeshParams));
				dtVcopy(m_orig, Params->orig);
				m_tileWidth = Params->tileWidth;
				m_tileHeight = Params->tileHeight;
				m_maxTiles = Params->maxTiles;
				m_tileLutSize = (int)dtNextPow2((uint)(Params->maxTiles / 4));
				if (0 == m_tileLutSize) m_tileLutSize = 1;
				m_tileLutMask = m_tileLutSize - 1;
				m_tiles = (dtMeshTile*)dtAlloc(sizeof(dtMeshTile) * m_maxTiles, dtAllocHint.DT_ALLOC_PERM);
				if (null == m_tiles)
					return DT_FAILURE | DT_OUT_OF_MEMORY;
				m_posLookup = (dtMeshTile**)dtAlloc(sizeof(dtMeshTile*) * m_tileLutSize, dtAllocHint.DT_ALLOC_PERM);
				if (null == m_posLookup)
					return DT_FAILURE | DT_OUT_OF_MEMORY;
				memset(m_tiles, 0, sizeof(dtMeshTile) * m_maxTiles);
				memset(m_posLookup, 0, sizeof(dtMeshTile*) * m_tileLutSize);
				m_nextFree = (dtMeshTile*)0;
				for (int i = m_maxTiles - 1; i >= 0; --i)
				{
					m_tiles[i].salt = 1;
					m_tiles[i].next = m_nextFree;
					m_nextFree = &m_tiles[i];
				}
				m_tileBits = dtIlog2((int)dtNextPow2((uint)Params->maxTiles));
				m_polyBits = dtIlog2((int)dtNextPow2((uint)Params->maxPolys));
				m_saltBits = dtMin(31, 32 - m_tileBits - m_polyBits);
				if (m_saltBits < 10)
					return DT_FAILURE | DT_INVALID_PARAM;
				return DT_SUCCESS;
			}
			public dtStatus init(byte* data, int dataSize, int flags)
			{
				dtMeshHeader* header = (dtMeshHeader*)data;
				if (header->magic != DT_NAVMESH_MAGIC)
					return DT_FAILURE | DT_WRONG_MAGIC;
				if (header->version != DT_NAVMESH_VERSION)
					return DT_FAILURE | DT_WRONG_VERSION;
				dtNavMeshParams Params = new dtNavMeshParams();
				dtVcopy(Params.orig, header->bmin);
				Params.tileWidth = header->bmax[0] - header->bmin[0];
				Params.tileHeight = header->bmax[2] - header->bmin[2];
				Params.maxTiles = 1;
				Params.maxPolys = header->polyCount;
				dtStatus status = init(&Params);
				if (dtStatusFailed(status))
					return status;
				return addTile(data, dataSize, flags, 0, (uint*)0);
			}
			public dtNavMeshParams* getParams()
			{
				return m_Params;
			}
			public dtStatus addTile(byte* data, int dataSize, int flags, dtTileRef lastRef, dtTileRef* result)
			{
				dtMeshHeader* header = (dtMeshHeader*)data;
				if (header->magic != DT_NAVMESH_MAGIC)
					return DT_FAILURE | DT_WRONG_MAGIC;
				if (header->version != DT_NAVMESH_VERSION)
					return DT_FAILURE | DT_WRONG_VERSION;
				if (m_polyBits < dtIlog2((int)dtNextPow2((uint)header->polyCount)))
					return DT_FAILURE | DT_INVALID_PARAM;
				if (null != getTileAt(header->x, header->y, header->layer))
					return DT_FAILURE | DT_ALREADY_OCCUPIED;
				dtMeshTile* tile = (dtMeshTile*)0;
				if (0 == lastRef)
				{
					if (null != m_nextFree)
					{
						tile = m_nextFree;
						m_nextFree = tile->next;
						tile->next = (dtMeshTile*)0;
					}
				}
				else
				{
					int tileIndex = (int)decodePolyIdTile(lastRef);
					if (tileIndex >= m_maxTiles)
						return DT_FAILURE | DT_OUT_OF_MEMORY;
					dtMeshTile* target = &m_tiles[tileIndex];
					dtMeshTile* prev = (dtMeshTile*)0;
					tile = m_nextFree;
					while (tile != null && tile != target)
					{
						prev = tile;
						tile = tile->next;
					}
					if (tile != target)
						return DT_FAILURE | DT_OUT_OF_MEMORY;
					if (null == prev)
						m_nextFree = tile->next;
					else
						prev->next = tile->next;
					tile->salt = decodePolyIdSalt(lastRef);
				}
				if (null == tile)
					return DT_FAILURE | DT_OUT_OF_MEMORY;
				int h = computeTileHash(header->x, header->y, m_tileLutMask);
				tile->next = m_posLookup[h];
				m_posLookup[h] = tile;
				int headerSize = dtAlign4(sizeof(dtMeshHeader));
				int vertsSize = dtAlign4(sizeof(float) * 3 * header->vertCount);
				int polysSize = dtAlign4(sizeof(dtPoly) * header->polyCount);
				int linksSize = dtAlign4(sizeof(dtLink) * (header->maxLinkCount));
				int detailMeshesSize = dtAlign4(sizeof(dtPolyDetail) * header->detailMeshCount);
				int detailVertsSize = dtAlign4(sizeof(float) * 3 * header->detailVertCount);
				int detailTrisSize = dtAlign4(sizeof(byte) * 4 * header->detailTriCount);
				int bvtreeSize = dtAlign4(sizeof(dtBVNode) * header->bvNodeCount);
				int offMeshLinksSize = dtAlign4(sizeof(dtOffMeshConnection) * header->offMeshConCount);
				byte* d = data + headerSize;
				tile->verts = dtGetThenAdvanceBufferPointer<float>(ref d, vertsSize);
				tile->polys = dtGetThenAdvanceBufferPointer<dtPoly>(ref d, polysSize);
				tile->links = dtGetThenAdvanceBufferPointer<dtLink>(ref d, linksSize);
				tile->detailMeshes = dtGetThenAdvanceBufferPointer<dtPolyDetail>(ref d, detailMeshesSize);
				tile->detailVerts = dtGetThenAdvanceBufferPointer<float>(ref d, detailVertsSize);
				tile->detailTris = dtGetThenAdvanceBufferPointer<byte>(ref d, detailTrisSize);
				tile->bvTree = dtGetThenAdvanceBufferPointer<dtBVNode>(ref d, bvtreeSize);
				tile->offMeshCons = dtGetThenAdvanceBufferPointer<dtOffMeshConnection>(ref d, offMeshLinksSize);
				if (0 == bvtreeSize)
					tile->bvTree = (dtBVNode*)0;
				tile->linksFreeList = 0;
				tile->links[header->maxLinkCount - 1].next = DT_NULL_LINK;
				for (int i = 0; i < header->maxLinkCount - 1; ++i)
					tile->links[i].next = (uint)(i + 1);
				tile->header = header;
				tile->data = data;
				tile->dataSize = dataSize;
				tile->flags = flags;
				connectIntLinks(tile);
				@baseOffMeshLinks(tile);
				connectExtOffMeshLinks(tile, tile, -1);
				int MAX_NEIS = 32;
				dtMeshTile** neis = stackalloc dtMeshTile*[MAX_NEIS];
				int nneis;
				nneis = getTilesAt(header->x, header->y, neis, MAX_NEIS);
				for (int j = 0; j < nneis; ++j)
				{
					if (neis + j == tile)
						continue;
					connectExtLinks(tile, neis[j], -1);
					connectExtLinks(neis[j], tile, -1);
					connectExtOffMeshLinks(tile, neis[j], -1);
					connectExtOffMeshLinks(neis[j], tile, -1);
				}
				for (int i = 0; i < 8; ++i)
				{
					nneis = getNeighbourTilesAt(header->x, header->y, i, neis, MAX_NEIS);
					for (int j = 0; j < nneis; ++j)
					{
						connectExtLinks(tile, neis[j], i);
						connectExtLinks(neis[j], tile, dtOppositeTile(i));
						connectExtOffMeshLinks(tile, neis[j], i);
						connectExtOffMeshLinks(neis[j], tile, dtOppositeTile(i));
					}
				}
				if (null != result)
					*result = getTileRef(tile);
				return DT_SUCCESS;
			}
			public dtStatus removeTile(dtTileRef Ref, byte** data, int* dataSize)
			{
				if (0 == Ref)
					return DT_FAILURE | DT_INVALID_PARAM;
				uint tileIndex = decodePolyIdTile(Ref);
				uint tileSalt = decodePolyIdSalt(Ref);
				if ((int)tileIndex >= m_maxTiles)
					return DT_FAILURE | DT_INVALID_PARAM;
				dtMeshTile* tile = &m_tiles[tileIndex];
				if (tile->salt != tileSalt)
					return DT_FAILURE | DT_INVALID_PARAM;
				int h = computeTileHash(tile->header->x, tile->header->y, m_tileLutMask);
				dtMeshTile* prev = (dtMeshTile*)0;
				dtMeshTile* cur = m_posLookup[h];
				while (cur != null)
				{
					if (cur == tile)
					{
						if (prev != null)
							prev->next = cur->next;
						else
							m_posLookup[h] = cur->next;
						break;
					}
					prev = cur;
					cur = cur->next;
				}
				int MAX_NEIS = 32;
				dtMeshTile** neis = stackalloc dtMeshTile*[MAX_NEIS];
				int nneis;
				nneis = getTilesAt(tile->header->x, tile->header->y, neis, MAX_NEIS);
				for (int j = 0; j < nneis; ++j)
				{
					if (neis + j == tile) continue;
					unconnectLinks(neis[j], tile);
				}
				for (int i = 0; i < 8; ++i)
				{
					nneis = getNeighbourTilesAt(tile->header->x, tile->header->y, i, neis, MAX_NEIS);
					for (int j = 0; j < nneis; ++j)
						unconnectLinks(neis[j], tile);
				}
				if (0 != (tile->flags & (int)dtTileFlags.DT_TILE_FREE_DATA))
				{
					dtFree(tile->data);
					tile->data = (byte*)0;
					tile->dataSize = 0;
					if (data != null) *data = (byte*)0;
					if (dataSize != null) *dataSize = 0;
				}
				else
				{
					if (data != null) *data = tile->data;
					if (dataSize != null) *dataSize = tile->dataSize;
				}
				tile->header = (dtMeshHeader*)0;
				tile->flags = 0;
				tile->linksFreeList = 0;
				tile->polys = (dtPoly*)0;
				tile->verts = (float*)0;
				tile->links = (dtLink*)0;
				tile->detailMeshes = (dtPolyDetail*)0;
				tile->detailVerts = (float*)0;
				tile->detailTris = (byte*)0;
				tile->bvTree = (dtBVNode*)0;
				tile->offMeshCons = (dtOffMeshConnection*)0;
				//#if DT_POLYREF64
				//tile->salt = (tile->salt+1)& ((1<<DT_SALT_BITS)-1);
				//#else
				tile->salt = (uint)((tile->salt + 1) & ((1 << (int)m_saltBits) - 1));
				if (tile->salt == 0)
					tile->salt++;
				tile->next = m_nextFree;
				m_nextFree = tile;
				return DT_SUCCESS;
			}
			public void calcTileLoc(float* pos, ref int tx, ref int ty)
			{
				tx = (int)floorf((pos[0] - m_orig[0]) / m_tileWidth);
				ty = (int)floorf((pos[2] - m_orig[2]) / m_tileHeight);
			}
			public dtMeshTile* getTileAt(int x, int y, int layer)
			{
				int h = computeTileHash(x, y, m_tileLutMask);
				dtMeshTile* tile = m_posLookup[h];
				while (tile != null)
				{
					if (tile->header != null &&
					tile->header->x == x &&
					tile->header->y == y &&
					tile->header->layer == layer)
					{
						return tile;
					}
					tile = tile->next;
				}
				return (dtMeshTile*)0;
			}
			public int getTilesAt(int x, int y, dtMeshTile** tiles, int maxTiles)
			{
				int n = 0;
				int h = computeTileHash(x, y, m_tileLutMask);
				dtMeshTile* tile = m_posLookup[h];
				while (null != tile)
				{
					if (tile->header != null &&
					tile->header->x == x &&
					tile->header->y == y)
					{
						if (n < maxTiles)
							tiles[n++] = tile;
					}
					tile = tile->next;
				}
				return n;
			}
			public dtTileRef getTileRefAt(int x, int y, int layer)
			{
				int h = computeTileHash(x, y, m_tileLutMask);
				dtMeshTile* tile = m_posLookup[h];
				while (tile != null)
				{
					if (tile->header != null &&
					tile->header->x == x &&
					tile->header->y == y &&
					tile->header->layer == layer)
					{
						return getTileRef(tile);
					}
					tile = tile->next;
				}
				return 0;
			}
			public dtTileRef getTileRef(dtMeshTile* tile)
			{
				if (null == tile) return 0;
				uint it = (uint)(tile - m_tiles);
				return (dtTileRef)encodePolyId(tile->salt, it, 0);
			}
			public dtMeshTile* getTileByRef(dtTileRef Ref)
			{
				if (0 == Ref)
					return (dtMeshTile*)0;
				uint tileIndex = decodePolyIdTile((dtPolyRef)Ref);
				uint tileSalt = decodePolyIdSalt((dtPolyRef)Ref);
				if ((int)tileIndex >= m_maxTiles)
					return (dtMeshTile*)0;
				dtMeshTile* tile = &m_tiles[tileIndex];
				if (tile->salt != tileSalt)
					return (dtMeshTile*)0;
				return tile;
			}
			public int getMaxTiles()
			{
				return m_maxTiles;
			}
			public dtMeshTile* getTile(int i)
			{
				return &m_tiles[i];
			}
			public dtStatus getTileAndPolyByRef(dtPolyRef Ref, dtMeshTile** tile, dtPoly** poly)
			{
				if (0 == Ref) return DT_FAILURE;
				uint salt = 0, it = 0, ip = 0;
				decodePolyId(Ref, ref salt, ref it, ref ip);
				if (it >= (uint)m_maxTiles) return DT_FAILURE | DT_INVALID_PARAM;
				if (m_tiles[it].salt != salt || m_tiles[it].header == null) return DT_FAILURE | DT_INVALID_PARAM;
				if (ip >= (uint)m_tiles[it].header->polyCount) return DT_FAILURE | DT_INVALID_PARAM;
				*tile = &m_tiles[it];
				*poly = &m_tiles[it].polys[ip];
				return DT_SUCCESS;
			}
			public void getTileAndPolyByRefUnsafe(dtPolyRef Ref, dtMeshTile** tile, dtPoly** poly)
			{
				uint salt = 0, it = 0, ip = 0;
				decodePolyId(Ref, ref salt, ref it, ref ip);
				*tile = &m_tiles[it];
				*poly = &m_tiles[it].polys[ip];
			}
			public bool isValidPolyRef(dtPolyRef Ref)
			{
				if (0 == Ref) return false;
				uint salt = 0, it = 0, ip = 0;
				decodePolyId(Ref, ref salt, ref it, ref ip);
				if (it >= (uint)m_maxTiles) return false;
				if (m_tiles[it].salt != salt || m_tiles[it].header == null) return false;
				if (ip >= (uint)m_tiles[it].header->polyCount) return false;
				return true;
			}
			public dtPolyRef getPolyRefBase(dtMeshTile* tile)
			{
				if (null == tile) return 0;
				uint it = (uint)(tile - m_tiles);
				return encodePolyId(tile->salt, it, 0);
			}
			public dtStatus getOffMeshConnectionPolyEndPoints(dtPolyRef prevRef, dtPolyRef polyRef, float* startPos, float* endPos)
			{
				uint salt = 0, it = 0, ip = 0;
				if (0 == polyRef)
					return DT_FAILURE;
				decodePolyId(polyRef, ref salt, ref it, ref ip);
				if (it >= (uint)m_maxTiles) return DT_FAILURE | DT_INVALID_PARAM;
				if (m_tiles[it].salt != salt || m_tiles[it].header == null) return DT_FAILURE | DT_INVALID_PARAM;
				dtMeshTile* tile = &m_tiles[it];
				if (ip >= (uint)tile->header->polyCount) return DT_FAILURE | DT_INVALID_PARAM;
				dtPoly* poly = &tile->polys[ip];
				if (poly->getType() != (int)dtPolyTypes.DT_POLYTYPE_OFFMESH_CONNECTION)
					return DT_FAILURE;
				int idx0 = 0, idx1 = 1;
				for (uint i = poly->firstLink; i != DT_NULL_LINK; i = tile->links[i].next)
				{
					if (tile->links[i].edge == 0)
					{
						if (tile->links[i].Ref != prevRef)
						{
							idx0 = 1;
							idx1 = 0;
						}
						break;
					}
				}
				dtVcopy(startPos, &tile->verts[poly->verts[idx0] * 3]);
				dtVcopy(endPos, &tile->verts[poly->verts[idx1] * 3]);
				return DT_SUCCESS;
			}
			public dtOffMeshConnection* getOffMeshConnectionByRef(dtPolyRef Ref)
			{
				uint salt = 0, it = 0, ip = 0;
				if (0 == Ref)
					return null;
				decodePolyId(Ref, ref salt, ref it, ref ip);
				if (it >= (uint)m_maxTiles) return null;
				if (m_tiles[it].salt != salt || m_tiles[it].header == null) return null;
				dtMeshTile* tile = &m_tiles[it];
				if (ip >= (uint)tile->header->polyCount) return null;
				dtPoly* poly = &tile->polys[ip];
				if (poly->getType() != (int)dtPolyTypes.DT_POLYTYPE_OFFMESH_CONNECTION)
					return null;
				uint idx = (uint)(ip - tile->header->offMeshBase);
				dtAssert(idx < (uint)tile->header->offMeshConCount);
				return &tile->offMeshCons[idx];
			}
			public dtStatus setPolyFlags(dtPolyRef Ref, ushort flags)
			{
				if (0 == Ref) return DT_FAILURE;
				uint salt = 0, it = 0, ip = 0;
				decodePolyId(Ref, ref salt, ref it, ref ip);
				if (it >= (uint)m_maxTiles) return DT_FAILURE | DT_INVALID_PARAM;
				if (m_tiles[it].salt != salt || m_tiles[it].header == null) return DT_FAILURE | DT_INVALID_PARAM;
				dtMeshTile* tile = &m_tiles[it];
				if (ip >= (uint)tile->header->polyCount) return DT_FAILURE | DT_INVALID_PARAM;
				dtPoly* poly = &tile->polys[ip];
				poly->flags = flags;
				return DT_SUCCESS;
			}
			public dtStatus getPolyFlags(dtPolyRef Ref, ushort* resultFlags)
			{
				if (0 == Ref) return DT_FAILURE;
				uint salt = 0, it = 0, ip = 0;
				decodePolyId(Ref, ref salt, ref it, ref ip);
				if (it >= (uint)m_maxTiles) return DT_FAILURE | DT_INVALID_PARAM;
				if (m_tiles[it].salt != salt || m_tiles[it].header == null) return DT_FAILURE | DT_INVALID_PARAM;
				dtMeshTile* tile = &m_tiles[it];
				if (ip >= (uint)tile->header->polyCount) return DT_FAILURE | DT_INVALID_PARAM;
				dtPoly* poly = &tile->polys[ip];
				*resultFlags = poly->flags;
				return DT_SUCCESS;
			}
			public dtStatus setPolyArea(dtPolyRef Ref, byte area)
			{
				if (0 == Ref) return DT_FAILURE;
				uint salt = 0, it = 0, ip = 0;
				decodePolyId(Ref, ref salt, ref it, ref ip);
				if (it >= (uint)m_maxTiles) return DT_FAILURE | DT_INVALID_PARAM;
				if (m_tiles[it].salt != salt || m_tiles[it].header == null) return DT_FAILURE | DT_INVALID_PARAM;
				dtMeshTile* tile = &m_tiles[it];
				if (ip >= (uint)tile->header->polyCount) return DT_FAILURE | DT_INVALID_PARAM;
				dtPoly* poly = &tile->polys[ip];
				poly->setArea(area);
				return DT_SUCCESS;
			}
			public dtStatus getPolyArea(dtPolyRef Ref, byte* resultArea)
			{
				if (0 == Ref) return DT_FAILURE;
				uint salt = 0, it = 0, ip = 0;
				decodePolyId(Ref, ref salt, ref it, ref ip);
				if (it >= (uint)m_maxTiles) return DT_FAILURE | DT_INVALID_PARAM;
				if (m_tiles[it].salt != salt || m_tiles[it].header == null) return DT_FAILURE | DT_INVALID_PARAM;
				dtMeshTile* tile = &m_tiles[it];
				if (ip >= (uint)tile->header->polyCount) return DT_FAILURE | DT_INVALID_PARAM;
				dtPoly* poly = &tile->polys[ip];
				*resultArea = poly->getArea();
				return DT_SUCCESS;
			}
			public int getTileStateSize(dtMeshTile* tile)
			{
				if (null == tile) return 0;
				int headerSize = dtAlign4(sizeof(dtTileState));
				int polyStateSize = dtAlign4(sizeof(dtPolyState) * tile->header->polyCount);
				return headerSize + polyStateSize;
			}
			public dtStatus storeTileState(dtMeshTile* tile, byte* data, int maxDataSize)
			{
				int sizeReq = getTileStateSize(tile);
				if (maxDataSize < sizeReq)
					return DT_FAILURE | DT_BUFFER_TOO_SMALL;
				dtTileState* tileState = dtGetThenAdvanceBufferPointer<dtTileState>(ref data, dtAlign4(sizeof(dtTileState)));
				dtPolyState* polyStates = dtGetThenAdvanceBufferPointer<dtPolyState>(ref data, dtAlign4(sizeof(dtPolyState) * tile->header->polyCount));
				tileState->magic = DT_NAVMESH_STATE_MAGIC;
				tileState->version = DT_NAVMESH_STATE_VERSION;
				tileState->Ref = getTileRef(tile);
				for (int i = 0; i < tile->header->polyCount; ++i)
				{
					dtPoly* p = &tile->polys[i];
					dtPolyState* s = &polyStates[i];
					s->flags = p->flags;
					s->area = p->getArea();
				}
				return DT_SUCCESS;
			}
			public dtStatus restoreTileState(dtMeshTile* tile, byte* data, int maxDataSize)
			{
				int sizeReq = getTileStateSize(tile);
				if (maxDataSize < sizeReq)
					return DT_FAILURE | DT_INVALID_PARAM;
				dtTileState* tileState = dtGetThenAdvanceBufferPointer<dtTileState>(ref data, dtAlign4(sizeof(dtTileState)));
				dtPolyState* polyStates = dtGetThenAdvanceBufferPointer<dtPolyState>(ref data, dtAlign4(sizeof(dtPolyState) * tile->header->polyCount));
				if (tileState->magic != DT_NAVMESH_STATE_MAGIC)
					return DT_FAILURE | DT_WRONG_MAGIC;
				if (tileState->version != DT_NAVMESH_STATE_VERSION)
					return DT_FAILURE | DT_WRONG_VERSION;
				if (tileState->Ref != getTileRef(tile))
					return DT_FAILURE | DT_INVALID_PARAM;
				for (int i = 0; i < tile->header->polyCount; ++i)
				{
					dtPoly* p = &tile->polys[i];
					dtPolyState* s = &polyStates[i];
					p->flags = s->flags;
					p->setArea(s->area);
				}
				return DT_SUCCESS;
			}
			public dtPolyRef encodePolyId(uint salt, uint it, uint ip)
			{
				//#if DT_POLYREF64
				//return ((dtPolyRef)salt << (DT_POLY_BITS+DT_TILE_BITS))| ((dtPolyRef)it << DT_POLY_BITS)| (dtPolyRef)ip;
				//#else

				dtPolyRef x = salt << (int)(m_polyBits + m_tileBits);
				dtPolyRef y = it << (int)m_polyBits;
				dtPolyRef z = ip;
				dtPolyRef t = x | y | z;
				return t;
				//return (dtPolyRef)(((int)salt << (m_polyBits + m_tileBits)) | (it << (int)m_polyBits) | ip;
			}
			public void decodePolyId(dtPolyRef Ref, ref uint salt, ref uint it, ref uint ip)
			{
				//#if DT_POLYREF64
				// dtPolyRef saltMask = ((dtPolyRef)1<<DT_SALT_BITS)-1;
				// dtPolyRef tileMask = ((dtPolyRef)1<<DT_TILE_BITS)-1;
				// dtPolyRef polyMask = ((dtPolyRef)1<<DT_POLY_BITS)-1;
				//salt = (uint)((Ref >> (DT_POLY_BITS+DT_TILE_BITS))& saltMask);
				//it = (uint)((Ref >> DT_POLY_BITS)& tileMask);
				//ip = (uint)(Ref & polyMask);
				//#else
				dtPolyRef saltMask = (uint)((1 << (int)m_saltBits) - 1);
				dtPolyRef tileMask = (uint)((1 << (int)m_tileBits) - 1);
				dtPolyRef polyMask = (uint)((1 << (int)m_polyBits) - 1);
				salt = (Ref >> (int)(m_polyBits + m_tileBits)) & saltMask;
				it = (Ref >> (int)m_polyBits) & tileMask;
				ip = Ref & polyMask;
			}
			public uint decodePolyIdSalt(dtPolyRef Ref)
			{
				//#if DT_POLYREF64
				// dtPolyRef saltMask = ((dtPolyRef)1<<DT_SALT_BITS)-1;
				//return (uint)((Ref >> (DT_POLY_BITS+DT_TILE_BITS))& saltMask);
				//#else
				dtPolyRef saltMask = ((dtPolyRef)1 << (int)m_saltBits) - 1;
				return (Ref >> (int)(m_polyBits + m_tileBits)) & saltMask;
			}
			public uint decodePolyIdTile(dtPolyRef Ref)
			{
				//#if DT_POLYREF64
				// dtPolyRef tileMask = ((dtPolyRef)1<<DT_TILE_BITS)-1;
				//return (uint)((Ref >> DT_POLY_BITS)& tileMask);
				//#else
				dtPolyRef tileMask = ((dtPolyRef)1 << (int)m_tileBits) - 1;
				return (uint)((Ref >> (int)m_polyBits) & tileMask);
			}
			public uint decodePolyIdPoly(dtPolyRef Ref)
			{
				//#if DT_POLYREF64
				// dtPolyRef polyMask = ((dtPolyRef)1<<DT_POLY_BITS)-1;
				//return (uint)(Ref & polyMask);
				//#else
				dtPolyRef polyMask = ((dtPolyRef)1 << (int)m_polyBits) - 1;
				return (uint)(Ref & polyMask);
			}
			//            public uint dtNavMesh(ref dtNavMesh @dtNavMesh)
			//            {
			//#if DT_POLYREF64
			// dtPolyRef polyMask = ((dtPolyRef)1<<DT_POLY_BITS)-1;
			//return (uint)(Ref & polyMask);
			//#else
			//                dtPolyRef polyMask = ((dtPolyRef)1 << (int)m_polyBits) - 1;
			//                return (uint)(Ref & polyMask);
			//            }
			//            public dtNavMesh& operator=(ref dtNavMesh @dtNavMesh) 
			//{
			//#if DT_POLYREF64
			// dtPolyRef polyMask = ((dtPolyRef)1<<DT_POLY_BITS)-1;
			//return (uint)(Ref & polyMask);
			//#else
			// dtPolyRef polyMask = ((dtPolyRef)1 << m_polyBits) - 1;
			//return (uint) (Ref & polyMask);
			//}
			//public int getTilesAt(int x, int y, dtMeshTile** tiles, int maxTiles)
			//{
			//    int n = 0;
			//    int h = computeTileHash(x, y, m_tileLutMask);
			//    dtMeshTile* tile = m_posLookup[h];
			//    while (tile != null)
			//    {
			//        if (tile->header != null &&
			//        tile->header->x == x &&
			//        tile->header->y == y)
			//        {
			//            if (n < maxTiles)
			//                tiles[n++] = tile;
			//        }
			//        tile = tile->next;
			//    }
			//    return n;
			//}
			public int getNeighbourTilesAt(int x, int y, int side, dtMeshTile** tiles, int maxTiles)
			{
				int nx = x, ny = y;
				switch (side)
				{
					case 0: nx++; break;
					case 1: nx++; ny++; break;
					case 2: ny++; break;
					case 3: nx--; ny++; break;
					case 4: nx--; break;
					case 5: nx--; ny--; break;
					case 6: ny--; break;
					case 7: nx++; ny--; break;
				};
				return getTilesAt(nx, ny, tiles, maxTiles);
			}
			public int findConnectingPolys(float* va, float* vb, dtMeshTile* tile, int side, dtPolyRef* con, float* conarea, int maxcon)
			{
				if (null == tile) return 0;
				float* amin = stackalloc float[2], amax = stackalloc float[2];
				calcSlabEndPoints(va, vb, amin, amax, side);
				float apos = getSlabCoord(va, side);
				float* bmin = stackalloc float[2], bmax = stackalloc float[2];
				ushort m = (ushort)(DT_EXT_LINK | (ushort)side);
				int n = 0;
				dtPolyRef @base = getPolyRefBase(tile);
				for (int i = 0; i < tile->header->polyCount; ++i)
				{
					dtPoly* poly = &tile->polys[i];
					int nv = poly->vertCount;
					for (int j = 0; j < nv; ++j)
					{
						if (poly->neis[j] != m) continue;
						float* vc = &tile->verts[poly->verts[j] * 3];
						float* vd = &tile->verts[poly->verts[(j + 1) % nv] * 3];
						float bpos = getSlabCoord(vc, side);
						if (dtAbs(apos - bpos) > 0.01f)
							continue;
						calcSlabEndPoints(vc, vd, bmin, bmax, side);
						if (!overlapSlabs(amin, amax, bmin, bmax, 0.01f, tile->header->walkableClimb)) continue;
						if (n < maxcon)
						{
							conarea[n * 2 + 0] = dtMax(amin[0], bmin[0]);
							conarea[n * 2 + 1] = dtMin(amax[0], bmax[0]);
							con[n] = @base | (dtPolyRef)i;
							n++;
						}
						break;
					}
				}
				return n;
			}
			public void connectIntLinks(dtMeshTile* tile)
			{
				if (null == tile) return;
				dtPolyRef @base = getPolyRefBase(tile);
				for (int i = 0; i < tile->header->polyCount; ++i)
				{
					dtPoly* poly = &tile->polys[i];
					poly->firstLink = DT_NULL_LINK;
					if (poly->getType() == (int)dtPolyTypes.DT_POLYTYPE_OFFMESH_CONNECTION)
						continue;
					for (int j = poly->vertCount - 1; j >= 0; --j)
					{
						if (poly->neis[j] == 0 || (poly->neis[j] & DT_EXT_LINK) != 0) continue;
						uint idx = allocLink(tile);
						if (idx != DT_NULL_LINK)
						{
							dtLink* link = &tile->links[idx];
							link->Ref = @base | (dtPolyRef)(poly->neis[j] - 1);
							link->edge = (byte)j;
							link->side = 0xff;
							link->bmin = link->bmax = 0;
							link->next = poly->firstLink;
							poly->firstLink = idx;
						}
					}
				}
			}
			public void @baseOffMeshLinks(dtMeshTile* tile)
			{
				if (null == tile) return;
				dtPolyRef @base = getPolyRefBase(tile);
				float* halfExtents = stackalloc float[3];
				float* nearestPt = stackalloc float[3];
				for (int i = 0; i < tile->header->offMeshConCount; ++i)
				{
					dtOffMeshConnection* con = &tile->offMeshCons[i];
					dtPoly* poly = &tile->polys[con->poly];
					//float* halfExtents = stackalloc float[3] { con->rad, tile->header->walkableClimb, con->rad };
					halfExtents[0] = con->rad;
					halfExtents[1] = tile->header->walkableClimb;
					halfExtents[2] = con->rad;
					float* p = &con->pos[0];
					//float* nearestPt = stackalloc float[3];
					memset(nearestPt, 0, sizeof(float) * 3);
					dtPolyRef Ref = findNearestPolyInTile(tile, p, halfExtents, nearestPt);
					if (0 == Ref) continue;
					if (dtSqr(nearestPt[0] - p[0]) + dtSqr(nearestPt[2] - p[2]) > dtSqr(con->rad))
						continue;
					float* v = &tile->verts[poly->verts[0] * 3];
					dtVcopy(v, nearestPt);
					uint idx = allocLink(tile);
					if (idx != DT_NULL_LINK)
					{
						dtLink* link = &tile->links[idx];
						link->Ref = Ref;
						link->edge = 0;
						link->side = 0xff;
						link->bmin = link->bmax = 0;
						link->next = poly->firstLink;
						poly->firstLink = idx;
					}
					uint tidx = allocLink(tile);
					if (tidx != DT_NULL_LINK)
					{
						ushort landPolyIdx = (ushort)decodePolyIdPoly(Ref);
						dtPoly* landPoly = &tile->polys[landPolyIdx];
						dtLink* link = &tile->links[tidx];
						link->Ref = @base | con->poly;
						link->edge = 0xff;
						link->side = 0xff;
						link->bmin = link->bmax = 0;
						link->next = landPoly->firstLink;
						landPoly->firstLink = tidx;
					}
				}
			}
			public void connectExtLinks(dtMeshTile* tile, dtMeshTile* target, int side)
			{
				if (null == tile) return;
				dtPolyRef* nei = stackalloc dtPolyRef[4];
				float* neia = stackalloc float[4 * 2];
				for (int i = 0; i < tile->header->polyCount; ++i)
				{
					dtPoly* poly = &tile->polys[i];
					int nv = poly->vertCount;
					for (int j = 0; j < nv; ++j)
					{
						if ((poly->neis[j] & DT_EXT_LINK) == 0)
							continue;
						int dir = (int)(poly->neis[j] & 0xff);
						if (side != -1 && dir != side)
							continue;
						float* va = &tile->verts[poly->verts[j] * 3];
						float* vb = &tile->verts[poly->verts[(j + 1) % nv] * 3];
						//dtPolyRef* nei = stackalloc dtPolyRef[4];
						//float* neia = stackalloc float[4 * 2];
						memset(nei, 0, sizeof(dtPolyRef) * 4);
						memset(neia, 0, sizeof(float) * (4 * 2));
						int nnei = findConnectingPolys(va, vb, target, dtOppositeTile(dir), nei, neia, 4);
						for (int k = 0; k < nnei; ++k)
						{
							uint idx = allocLink(tile);
							if (idx != DT_NULL_LINK)
							{
								dtLink* link = &tile->links[idx];
								link->Ref = nei[k];
								link->edge = (byte)j;
								link->side = (byte)dir;
								link->next = poly->firstLink;
								poly->firstLink = idx;
								if (dir == 0 || dir == 4)
								{
									float tmin = (neia[k * 2 + 0] - va[2]) / (vb[2] - va[2]);
									float tmax = (neia[k * 2 + 1] - va[2]) / (vb[2] - va[2]);
									if (tmin > tmax)
										dtSwap(ref tmin, ref tmax);
									link->bmin = (byte)roundf(dtClamp(tmin, 0.0f, 1.0f) * 255.0f);
									link->bmax = (byte)roundf(dtClamp(tmax, 0.0f, 1.0f) * 255.0f);
								}
								else if (dir == 2 || dir == 6)
								{
									float tmin = (neia[k * 2 + 0] - va[0]) / (vb[0] - va[0]);
									float tmax = (neia[k * 2 + 1] - va[0]) / (vb[0] - va[0]);
									if (tmin > tmax)
										dtSwap(ref tmin, ref tmax);
									link->bmin = (byte)roundf(dtClamp(tmin, 0.0f, 1.0f) * 255.0f);
									link->bmax = (byte)roundf(dtClamp(tmax, 0.0f, 1.0f) * 255.0f);
								}
							}
						}
					}
				}
			}
			public void connectExtOffMeshLinks(dtMeshTile* tile, dtMeshTile* target, int side)
			{
				if (null == tile) return;
				byte oppositeSide = (byte)((side == -1) ? 0xff : (byte)dtOppositeTile(side));
				float* halfExtents = stackalloc float[3];
				float* nearestPt = stackalloc float[3];
				for (int i = 0; i < target->header->offMeshConCount; ++i)
				{
					dtOffMeshConnection* targetCon = &target->offMeshCons[i];
					if (targetCon->side != oppositeSide)
						continue;
					dtPoly* targetPoly = &target->polys[targetCon->poly];
					if (targetPoly->firstLink == DT_NULL_LINK)
						continue;
					//float* halfExtents = stackalloc float[3] { targetCon->rad, target->header->walkableClimb, targetCon->rad };
					halfExtents[0] = targetCon->rad;
					halfExtents[1] = target->header->walkableClimb;
					halfExtents[2] = targetCon->rad;
					float* p = &targetCon->pos[3];
					//float* nearestPt = stackalloc float[3];
					memset(nearestPt, 0, sizeof(float) * 3);
					dtPolyRef Ref = findNearestPolyInTile(tile, p, halfExtents, nearestPt);
					if (0 == Ref)
						continue;
					if (dtSqr(nearestPt[0] - p[0]) + dtSqr(nearestPt[2] - p[2]) > dtSqr(targetCon->rad))
						continue;
					float* v = &target->verts[targetPoly->verts[1] * 3];
					dtVcopy(v, nearestPt);
					uint idx = allocLink(target);
					if (idx != DT_NULL_LINK)
					{
						dtLink* link = &target->links[idx];
						link->Ref = Ref;
						link->edge = (byte)1;
						link->side = oppositeSide;
						link->bmin = link->bmax = 0;
						link->next = targetPoly->firstLink;
						targetPoly->firstLink = idx;
					}
					if (0 != (targetCon->flags & DT_OFFMESH_CON_BIDIR))
					{
						uint tidx = allocLink(tile);
						if (tidx != DT_NULL_LINK)
						{
							ushort landPolyIdx = (ushort)decodePolyIdPoly(Ref);
							dtPoly* landPoly = &tile->polys[landPolyIdx];
							dtLink* link = &tile->links[tidx];
							link->Ref = getPolyRefBase(target) | (dtPolyRef)(targetCon->poly);
							link->edge = 0xff;
							link->side = (byte)(side == -1 ? 0xff : side);
							link->bmin = link->bmax = 0;
							link->next = landPoly->firstLink;
							landPoly->firstLink = tidx;
						}
					}
				}
			}
			public void unconnectLinks(dtMeshTile* tile, dtMeshTile* target)
			{
				if (null == tile || null == target) return;
				uint targetNum = decodePolyIdTile(getTileRef(target));
				for (int i = 0; i < tile->header->polyCount; ++i)
				{
					dtPoly* poly = &tile->polys[i];
					uint j = poly->firstLink;
					uint pj = DT_NULL_LINK;
					while (j != DT_NULL_LINK)
					{
						if (decodePolyIdTile(tile->links[j].Ref) == targetNum)
						{
							uint nj = tile->links[j].next;
							if (pj == DT_NULL_LINK)
								poly->firstLink = nj;
							else
								tile->links[pj].next = nj;
							freeLink(tile, j);
							j = nj;
						}
						else
						{
							pj = j;
							j = tile->links[j].next;
						}
					}
				}
			}
			public int queryPolygonsInTile(dtMeshTile* tile, float* qmin, float* qmax, dtPolyRef* polys, int maxPolys)
			{
				if (tile->bvTree != null)
				{
					dtBVNode* node = &tile->bvTree[0];
					dtBVNode* end = &tile->bvTree[tile->header->bvNodeCount];
					float* tbmin = tile->header->bmin;
					float* tbmax = tile->header->bmax;
					float qfac = tile->header->bvQuantFactor;
					ushort* bmin = stackalloc ushort[3], bmax = stackalloc ushort[3];
					float minx = dtClamp(qmin[0], tbmin[0], tbmax[0]) - tbmin[0];
					float miny = dtClamp(qmin[1], tbmin[1], tbmax[1]) - tbmin[1];
					float minz = dtClamp(qmin[2], tbmin[2], tbmax[2]) - tbmin[2];
					float maxx = dtClamp(qmax[0], tbmin[0], tbmax[0]) - tbmin[0];
					float maxy = dtClamp(qmax[1], tbmin[1], tbmax[1]) - tbmin[1];
					float maxz = dtClamp(qmax[2], tbmin[2], tbmax[2]) - tbmin[2];
					bmin[0] = (ushort)((int)(qfac * minx) & 0xfffe);
					bmin[1] = (ushort)((int)(qfac * miny) & 0xfffe);
					bmin[2] = (ushort)((int)(qfac * minz) & 0xfffe);
					bmax[0] = (ushort)((int)(qfac * maxx + 1) | 1);
					bmax[1] = (ushort)((int)(qfac * maxy + 1) | 1);
					bmax[2] = (ushort)((int)(qfac * maxz + 1) | 1);
					dtPolyRef @base = getPolyRefBase(tile);
					int n = 0;
					while (node < end)
					{
						bool overlap = dtOverlapQuantBounds(bmin, bmax, node->bmin, node->bmax);
						bool isLeafNode = node->i >= 0;
						if (isLeafNode && overlap)
						{
							if (n < maxPolys)
								polys[n++] = @base | (dtPolyRef)node->i;
						}
						if (overlap || isLeafNode)
							node++;
						else
						{
							int escapeIndex = -node->i;
							node += escapeIndex;
						}
					}
					return n;
				}
				else
				{
					float* bmin = stackalloc float[3], bmax = stackalloc float[3];
					int n = 0;
					dtPolyRef @base = getPolyRefBase(tile);
					for (int i = 0; i < tile->header->polyCount; ++i)
					{
						dtPoly* p = &tile->polys[i];
						if (p->getType() == (int)dtPolyTypes.DT_POLYTYPE_OFFMESH_CONNECTION)
							continue;
						float* v = &tile->verts[p->verts[0] * 3];
						dtVcopy(bmin, v);
						dtVcopy(bmax, v);
						for (int j = 1; j < p->vertCount; ++j)
						{
							v = &tile->verts[p->verts[j] * 3];
							dtVmin(bmin, v);
							dtVmax(bmax, v);
						}
						if (dtOverlapBounds(qmin, qmax, bmin, bmax))
						{
							if (n < maxPolys)
								polys[n++] = @base | (dtPolyRef)i;
						}
					}
					return n;
				}
			}
			public dtPolyRef findNearestPolyInTile(dtMeshTile* tile, float* center, float* halfExtents, float* nearestPt)
			{
				float* bmin = stackalloc float[3], bmax = stackalloc float[3];
				dtVsub(bmin, center, halfExtents);
				dtVadd(bmax, center, halfExtents);
				dtPolyRef* polys = stackalloc dtPolyRef[128];
				int polyCount = queryPolygonsInTile(tile, bmin, bmax, polys, 128);
				dtPolyRef nearest = 0;
				float nearestDistanceSqr = FLT_MAX;
				float* closestPtPoly = stackalloc float[3];
				float* diff = stackalloc float[3];
				for (int i = 0; i < polyCount; ++i)
				{
					dtPolyRef Ref = polys[i];
					//float* closestPtPoly = stackalloc float[3];
					//float* diff = stackalloc float[3];
					memset(closestPtPoly, 0, sizeof(float) * 3);
					memset(diff, 0, sizeof(float) * 3);
					bool posOverPoly = false;
					float d;
					closestPointOnPoly(Ref, center, closestPtPoly, &posOverPoly);
					dtVsub(diff, center, closestPtPoly);
					if (posOverPoly)
					{
						d = dtAbs(diff[1]) - tile->header->walkableClimb;
						d = d > 0 ? d * d : 0;
					}
					else
					{
						d = dtVlenSqr(diff);
					}
					if (d < nearestDistanceSqr)
					{
						dtVcopy(nearestPt, closestPtPoly);
						nearestDistanceSqr = d;
						nearest = Ref;
					}
				}
				return nearest;
			}
			public bool getPolyHeight(dtMeshTile* tile, dtPoly* poly, float* pos, float* height)
			{
				if (poly->getType() == (int)dtPolyTypes.DT_POLYTYPE_OFFMESH_CONNECTION)
					return false;
				uint ip = (uint)(poly - tile->polys);
				dtPolyDetail* pd = &tile->detailMeshes[ip];
				float* verts = stackalloc float[DT_VERTS_PER_POLYGON * 3];
				int nv = poly->vertCount;
				for (int i = 0; i < nv; ++i)
					dtVcopy(&verts[i * 3], &tile->verts[poly->verts[i] * 3]);
				if (!dtPointInPolygon(pos, verts, nv))
					return false;
				if (null == height)
					return true;
				float** v = stackalloc float*[3];
				for (int j = 0; j < pd->triCount; ++j)
				{
					byte* t = &tile->detailTris[(pd->triBase + j) * 4];
					//float** v = stackalloc float*[3];
					memset(v, 0, sizeof(float*) * 3);
					for (int k = 0; k < 3; ++k)
					{
						if (t[k] < poly->vertCount)
							v[k] = &tile->verts[poly->verts[t[k]] * 3];
						else
							v[k] = &tile->detailVerts[(pd->vertBase + (t[k] - poly->vertCount)) * 3];
					}
					float h = 0f;
					if (dtClosestHeightPointTriangle(pos, v[0], v[1], v[2], ref h))
					{
						*height = h;
						return true;
					}
				}
				float* closest = stackalloc float[3];
				closestPointOnDetailEdges(false, tile, poly, pos, closest);
				*height = closest[1];
				return true;
			}
			public void closestPointOnPoly(dtPolyRef Ref, float* pos, float* closest, bool* posOverPoly)
			{
				dtMeshTile* tile = (dtMeshTile*)0;
				dtPoly* poly = (dtPoly*)0;
				getTileAndPolyByRefUnsafe(Ref, &tile, &poly);
				dtVcopy(closest, pos);
				if (getPolyHeight(tile, poly, pos, &closest[1]))
				{
					if (posOverPoly != null)
						*posOverPoly = true;
					return;
				}
				if (posOverPoly != null)
					*posOverPoly = false;
				if (poly->getType() == (int)dtPolyTypes.DT_POLYTYPE_OFFMESH_CONNECTION)
				{
					float* v0 = &tile->verts[poly->verts[0] * 3];
					float* v1 = &tile->verts[poly->verts[1] * 3];
					float t = 0f;
					dtDistancePtSegSqr2D(pos, v0, v1, ref t);
					dtVlerp(closest, v0, v1, t);
					return;
				}
				closestPointOnDetailEdges(true, tile, poly, pos, closest);
			}
		}
	}
}